/*
 * DephtFirstSearchSorter.java - Copyright May 14, 2012 Z Networks Group, Inc. All rights reserved.
 * Z Networks Group PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package com.andromeda.util.dependency;

import java.util.*;

/**
 * Usa el algoritmo de búsqueda invertida, no puede detectar ciclos por ahora.
 *
 * @author Dickinson Roman Arismendy Torres
 */
public class DephtFirstSearchSorter extends AbstractTopologicalSorter {

    @Override
    public List<Dependent> sort(Set<? extends Dependent> dependents) {
        return depthFirstSearchSorting(dependents);
    }

    private List<Dependent> depthFirstSearchSorting(Set<? extends Dependent> nodes) {
        List<Dependent> sorted = new ArrayList<Dependent>();
        Set<Dependent> visitedNodes = new HashSet<Dependent>();
        Set<Dependent> independents = findFirstDependents(nodes);
        for (Dependent node : independents) {
            visit(nodes, node, visitedNodes, sorted);
        }
        Collections.reverse(sorted);
        return sorted;
    }

    private void visit(Set<? extends Dependent> allNodes, Dependent node,
            Set<Dependent> visitedNodes, List<Dependent> sorted) {
        if (!visitedNodes.contains(node)) {
            visitedNodes.add(node);
            for (Dependent dependent : getDependents(node, allNodes)) {
                visit(allNodes, dependent, visitedNodes, sorted);
            }
            sorted.add(node);
        }
    }
}
